| 1. |
|
|
| 2. |
- Damaschke, Peter, 1963, et al.
(author)
-
Competitive Freshness Algorithms for Wait-free Data Objects
- 2005
-
Reports (other academic/artistic)abstract
- Wait-free concurrent data objects are widely used in multiprocessor systems and real-time systems. Their popularity results from the fact that they avoid locking and that concurrent operations on such data objects are guaranteed to finish in a bounded number of steps regardless of the other operations interference. The data objects allow high access parallelism and guarantee correctness of the concurrent access with respect to its semantics. In such a highly-concurrent environment, where write-operations update the object state concurrently with read-operations, the age/freshness of the state returned by a read-operation is a significant measure of the object quality.In this paper, we first propose a freshness measure for wait-free concurrent data objects. Subsequently, we model the freshness problem as an online problem and present two algorithms for the problem. The first one is an optimal deterministic algorithm with freshness competitive ratio $\sqrt{\alpha}$, where $\alpha$ is a function of execution-time upper-bound of wait-free operations. The second one is a competitive randomized algorithm with freshness competitive ratio $\frac{\ln \alpha}{1 + \ln 2 - \frac{2}{\sqrt{\alpha}}}$.
|
|
| 3. |
- Damaschke, Peter, 1963, et al.
(author)
-
One-Way Trading with Time-Varying Exchange Rate Bounds
- 2005
-
Reports (other academic/artistic)abstract
- One-way trading is a basic online problem in finance. Since its optimal solution is given by a simple formula (however with difficult analysis), the problem is attractive as a target to which other practical online problems can betransformed. However, there are still natural online problems that do not fit in the known variants of one-way trading. We present some new models where the bounds of exchange rates are not constant but vary with time in certain ways. The first model, where the (logarithmic) exchange rate has limited decay speed, arises from an issue in distributed data structures, namely to maximize the(appropriately defined) freshness of values in concurrent objects. For this model we prove a lower bound on the competitive ratio which is nearly optimal, i.e., upto a small constant factor. Clearly, the lower bound holds also against stronger adversaries. Then, we give an optimal algorithm in a model where only the maximal allowed exchange rate decreases with time, but the actual exchange rates may jump arbitrarily within this frame. We have chosen this more powerful adversary model afterwards because some applications does not make use of the limited decay speed. In fact, we adapt the optimal threat-based algorithm of El-Yaniv et al. (2001) to our case. Our numerical experiments suggest that this algorithm is still not too far from the lower bound for the weaker adversary. This isexplained by the observation that slowly increasing exchange rates seem to be the worst case for the online player.
|
|
| 4. |
- Damaschke, Peter, 1963, et al.
(author)
-
Online search with time-varying price bounds
- 2009
-
In: Algorithmica. - : Springer Science and Business Media LLC. - 0178-4617 .- 1432-0541. ; 55:4, s. 619-642
-
Journal article (peer-reviewed)abstract
- Online search is a basic online problem. The fact that its optimal deterministic/randomized solutions are given by simple formulas (however with difficult analysis) makes the problem attractive as a target to which other practical online problems can be transformed to find optimal solutions. However, since the upper/lower bounds of prices in available models are constant, natural online problems in which these bounds vary with time do not fit in the available models. We present two new models where the bounds of prices are not constant but vary with time in certain ways. The first model, where the upper and lower bounds of (logarithmic) prices have decay speed, arises from a problem in concurrent data structures, namely to maximize the (appropriately defined) freshness of data in concurrent objects. For this model we present an optimal deterministic algorithm and a nearly-optimal randomized algorithm. We also prove a lower bound of competitive ratios of randomized algorithms. The second model is inspired by the fact that some applications do not utilize the decay speed of the lower bound of prices in the first model. In the second model, only the upper bound decreases arbitrarily with time and the lower bound is constant. Clearly, the lower bound of competitive ratios proved for the first model holds also against the stronger adversary in the second model. For the second model, we present an optimal randomized algorithm. Our numerical experiments on the freshness problem show that this new algorithm achieves much better/smaller competitive ratios than previous algorithms do.
|
|
